package com.leetcode.partition5;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2021/11/3 9:10
 */
public class LC407接雨水2 {

    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static int trapRainWater(int[][] heightMap) {
        return dijkstra(heightMap);
    }

    public static void main(String[] args) {
        int[][] heightMap = {
                {1, 4, 3, 1, 3, 2},
                {3, 2, 1, 3, 2, 4},
                {2, 3, 1, 2, 3, 1},
                {3, 3, 3, 3, 3, 3}
        };
        System.out.println(trapRainWater(heightMap));
    }

    private static int dijkstra(int[][] heightMap) {
        //https://leetcode-cn.com/problems/trapping-rain-water-ii/solution/gong-shui-san-xie-jing-dian-dijkstra-yun-13ik/
        int m = heightMap.length, n = heightMap[0].length, answer = 0;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        boolean[][] visited = new boolean[m][n];
        //超级源点到达所有边界的距离都为0，4个边界先入堆
        for (int i = 0; i < m; i++) {
            minHeap.add(new int[]{i, 0, heightMap[i][0]});
            minHeap.add(new int[]{i, n - 1, heightMap[i][n - 1]});
            visited[i][0] = visited[i][n - 1] = true;
        }
        for (int j = 1; j < n - 1; j++) {
            minHeap.add(new int[]{0, j, heightMap[0][j]});
            minHeap.add(new int[]{m - 1, j, heightMap[m - 1][j]});
            visited[0][j] = visited[m - 1][j] = true;
        }
        while (!minHeap.isEmpty()) {
            int[] cur = minHeap.poll();
            int x = cur[0], y = cur[1], height = cur[2];
            for (int[] dir : dirs) {
                int x1 = x + dir[0], y1 = y + dir[1];
                //限制越界和未被访问
                if (x1 < 0 || x1 >= m || y1 < 0 || y1 >= n || visited[x1][y1]) continue;
                if (height > heightMap[x1][y1]) {
                    System.out.printf("(%d, %d, %d)->(%d, %d, %d) %d\n", x, y, height, x1, y1, heightMap[x1][y1], height - heightMap[x1][y1]);
                    answer += height - heightMap[x1][y1];
                }
                //计算了最小高度的节点，最小高度节点的高就应该是当前节点的高，相当于填满
                minHeap.add(new int[]{x1, y1, Math.max(heightMap[x1][y1], height)});
                visited[x1][y1] = true;
            }
        }
        return answer;
    }
}
